package offer;

/**
 * @Author Elephas
 * @Date 2022/2/20
 **/
@FunctionalInterface
public interface Convert {
    String convert(String s, int numRows);
}
class ConvertImpl1 implements Convert{
    static final String TEST_01_S = "PAYPALISHIRING";
    static final int TEST_01_NUMROWS = 3;
    static final String TEST_01_ANSWER = "PAHNAPLSIIGYIR";
    public static void main(String[] args){
        String ans = new ConvertImpl1().convert(TEST_01_S, TEST_01_NUMROWS);
        System.out.println(ans.equals(TEST_01_ANSWER));
    }

    /**
     * 字符串s的长度为n，z形状为r列，时间复杂度为o(n*r),空间复杂度为o(n*r)
     * @param s
     * @param numRows
     * @return
     */
    @Override
    public String convert(String s, int numRows) {
        int numColumns = s.length(), n = numColumns;
        char[][] map = new char[numRows][numColumns];
        for(int i = 0; i < numRows; i++){
            for(int j = 0; j < numColumns; j++){
                map[i][j] = '#';
            }
        }
        int curLen = 0, curCol = 0;
        while(curLen < n){
            // 上到下
            for(int i = 0; i < numRows && curLen < n; i++){
                map[i][curCol] = s.charAt(curLen);
                curLen++;
            }
            // 斜下到斜上
            int i = numRows - 2, j = curCol + 1;
            while(i > 0 && curLen < n){
                map[i][j] = s.charAt(curLen);
                curLen++;
                i--;
                j++;
            }
            curCol = j;
        }
        StringBuilder ans = new StringBuilder();
        for(int i = 0; i < numRows; i++){
            for(int j = 0; j < numColumns; j++){
                if(map[i][j] != '#'){
                    ans.append(map[i][j]);
                }
            }
        }
        return ans.toString();
    }
}

class ConvertImpl2 implements Convert{

    /**
     * 时间o(n),空间o(1）的解法,转换后的坐标是可计算的
     * @param s
     * @param numRows
     * @return
     */
    @Override

    public String convert(String s, int numRows){
        int n = s.length(), r = numRows;
        if(r == 1 || r > n){
            return s;
        }
        String ans = "";
        int t = r * 2 - 2;
        for(int i = 0; i < r; i++){
            for(int j = 0; j + i < n; j+=t ){
                ans += s.charAt(j + i);
                if(0 < i && i < r - 1 && j + t - i < n){
                    ans += s.charAt(j + t - i);
                }
            }
        }
        return ans;
    }
}